COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Exercises - CS206
C00012 00003	(DEFPROP HS
C00016 ENDMK
C⊗;
Exercises - CS206

Problems to be assigned will be selected from these.

For problems 1 to 12, write Lisp functions as described.

1.    %3alt%2[%3u, m, n%2]%1 takes every %3n%1th element of the list %3u%1 starting
with the %3m%1th.  Write a recursive defintion of %3alt%2[%3u, m, n%2].%1
.SKIP 2
2.      %3odds u%1 is a list of the elements of the list %3u%1 that occur in %3u%1
an odd number of times.  Write the fastest definition of %3odds %1 that you can.
Give several if you like, but be sure to have one that works.
.SKIP 2
3.	%3commontail%2[%3u,v%2]%1 is the longest common sublist of
%3u%1 and %3v%1 ending with the ends of the lists.  Thus
%3commontail%5[(A B C D E),(A C D E)] = (C D E).
.SKIP 2
4.	%3pairs%2[%3u,v%2]%1   is  the  list of all pairs of elements, each
pair taking one element from  %3u%1  and one from  %3v%1. Thus

	%3pairs%5[(A B C),(D E)] = ((A D) (A E) (B D) (B E) (C D) (C E)).%1

Observe the ordering given in the example.
.SKIP 2
5.	a. %3rcycle%2[%3u%2]%1  is obtained from the list  %3u%1  by moving the
last element to the first position.  Thus

	%3rcycle%5[(A B C D)] = (D A B C).%1

	b. %3lcycle%2[%3u%2]%1  is obtained from the list   %3u%1   by  moving  the
first element to the last position.  Thus

	%3lcycle%5[(A B C D)] = (B C D A).%1
.SKIP 2
6.	%3permut u%1 is a list of all the permutations of the
list %3u%1.  Thus

	%3permut %5(A B C) = ((A B C)(A C B)(B A C)(B C A)(C A B)(C B A)).

The order in which the permutations are listed is not important here.
.SKIP 2
7.	%3conn%2[%3g%2]%1 is true if and only if the directed graph %3g%1 represented
as described in chapter 1 of the class notes is connected in the sense
that every vertex is reachable from every other vertex.  Write a LISP
function for %3conn%1.
.SKIP 2
8.      Let a graph %3g%1 be described as in chapter 1 of the notes and suppose that
whenever there is an edge from %3x%1 to %3y%1 there is also an edge from %3y%1
to %3x%1.  A component of the graph is a collection of vertices which are all connected to
each other by edge paths but not connected to any other vertices.  Write a function
to determine the number of components.
.SKIP 2
9.	%3testr%2[%3u,f,p,w%2]%1  is obtained from the S-expression   %3u%1   as
follows:  If no subexpression of  %3u%1  satisfies the predicate  %3p%1, then
%3w%2[%3u%2]%1  is the result.  If there is such an expression, say   %3m%1,  then
%3f%2[%3m%2]%1   is  the result. If there are several such  %3m%1, then any  %3f%2[%3m%2]%1 
will do.
.SKIP 2
10.	Write a function to convert a list  of  English  words  to
"Pig Latin."

Each English word is translated to pig latin by the following rules:
.BEGIN INDENT 8,8,0
1.  if  the  first letter of the English word is a vowel then the pig
latin translation is the same as the English word.

2. Otherwise, rotate the first letter of the word to the end  of  the
word  and  repeat  until the first letter becomes a vowel.    Add the
letters "AY" to the end of the word you have and that is the answer.

3.  For the puposes of this problem, vowels are A E I O and U.

4.  Assume every English word contains at least one vowel.
.END

.NOFILL

example:

%3piglatin%5[(I LIKE LISP BETTER THAN PIG LATIN)] =
	(I IKELAY ISPLAY ETTERBAY ANTHAY IGPAY ATINLAY)
.FILL
%1there are two functions in LISP that you will need:

	%3explode %5APPLE = (A P P L E)
%1and
	%3readlist %5(A P P L E) = APPLE%1
.SKIP 2
11.	Let the complex number  %3x%2+%3iy%1  be represented as an S-expression
by the pair  (%3x . y%1); thus  3+4%3i%1  is represented as  (3 . 4).  Write an
evaluator  %3ceval%2[%3e%2]%1  where  %3e%1  is an algebraic expression in  PLUS, TIMES,
and complex and real constants.

	For example, we have

	%3ceval%5[(PLUS (3 . 4) 7 (TIMES (1 . 2) (2 . 1)))] = (10 . 9).%1
.SKIP 2
12.	Let %3u%1 and %3v%1 be  two  S-expressions.   Certain  of  the  atoms
occurring  in  these  expressions  are regarded as variables, and the
propositional expression %3isvar%2[%3x%2]%1 will be true if %3x%1 is a variable.  %3%3u%1
and %3v%1 may be assumed to have no variables in common.

	If there are substitutions for the variables in %3u%1 and %3v%1  that
make %3u%1 and %3v%1 the same expression, then %3match %2[%3u,v%2]%1 is a list of pairs
such that

	%3e %2=%3sublis%2[%3match%2[%3u,v%2],%3u%2] = %3sublis%2[%3match%2[%3u,v%2],%3v%2]%1 for the most
general %3e%1.  Otherwise, %3match%2[%3u,v%2] = NO%1.

	For example,
.NOFILL

	%3match%5[(PLUS(TIMES X Y) Z), (PLUS ∪ (PLUS W Z))]   =
	((U . TIMES X Y)) (Z . PLUS W Z)))
.FILL
%1where the single letters are regarded as variables.
.SKIP 2
13.     The %3n%1th Fibonacci number is defined by the equations
.NOFILL

	%5F%60%5 = 1
	F%61%5 = 1
	F%6n+2%5 = F%6n+1%5 + F%6n%1.
.FILL
Thus we have F%62%5 = 2, F%63%5 = 3, F%64%5 = 5, F%65%5 = 8%1, etc.

This definition translates into LISP as
.NOFILL

	F%6n%2 ← %4if%3 n%2 = 0 %2∨ %3n%2 = 1 %4then%2 1 %4else%5 F%62n-2%2 + F%6n-1%1.

	What bad thing will happen if we try to compute F%6100%1 using this definition?
	Write a new LISP definition of F%6n%1 not suffering from this problem.
.FILL
.SKIP 2
14.	Devise a list structure representation of positions in the
game of tic-tac-toe (noughts and crosses), and write functions %3ter p%1,
which tells whether the game is over in position %3p%1,
%3imval p%1 which tells the value of the game for a terminated
position (use -1, 0 and 1 for values), and %3successors p%1 which
gives the successors to a non-terminating position %3p%1.  Make no
special effort to achieve efficiency.
.SKIP 2
15.	Compare the  the compilation of %2∧%1's and %2∨%1's  in LCOM0 and
LCOM4.  Give  the simplest example you can of an expression for which
LCOM4 generates better code indicating the code generated by each.


(DEFPROP HS
 (NIL ALT
      ODDS
      ODDS1
      ENTER
      COMMONTAIL
      COMMONR
      RCYCLE
      LCYCLE
      PERMUT
      PERMUT1
      PERMUT2
      REV1
      CONN
      COMP
      MERGCOMPS
      MERGCOMP
      UNION)
VALUE)

(DEFPROP ALT
 (LAMBDA (U M N) (COND ((NULL U) NIL) ((EQ M 1) (CONS (CAR U) (ALT (CDR U) N N))) (T (ALT (CDR U) (SUB1 M) N))))
EXPR)

(DEFPROP ODDS
 (LAMBDA (U) (ODDS1 U NIL))
EXPR)

(DEFPROP ODDS1
 (LAMBDA (U V) (COND ((NULL U) V) (T (ODDS1 (CDR U) (ENTER (CAR U) V)))))
EXPR)

(DEFPROP ENTER
 (LAMBDA (X V) (COND ((NULL V) (LIST X)) ((EQUAL (CAR V) X) (CDR V)) (T (CONS (CAR V) (ENTER X (CDR V))))))
EXPR)

(DEFPROP COMMONTAIL
 (LAMBDA (U V) (COMMONR (REVERSE U) (REVERSE V) NIL))
EXPR)

(DEFPROP COMMONR
 (LAMBDA(U V W)
  (COND	((OR (NULL U) (NULL V) (NOT (EQUAL (CAR U) (CAR V)))) W)
	(T (COMMONR (CDR U) (CDR V) (CONS (CAR U) W)))))
EXPR)

(DEFPROP RCYCLE
 (LAMBDA (U) ((LAMBDA (V) (CONS (CAR V) (REVERSE (CDR V)))) (REVERSE U)))
EXPR)

(DEFPROP LCYCLE
 (LAMBDA (U) (APPEND (CDR U) (LIST (CAR U))))
EXPR)

(DEFPROP PERMUT
 (LAMBDA (U) (COND ((NULL U) (QUOTE (NIL))) (T (PERMUT1 (CAR U) (PERMUT (CDR U))))))
EXPR)

(DEFPROP PERMUT1
 (LAMBDA (X W) (COND ((NULL W) NIL) (T (APPEND (PERMUT2 NIL X (CAR W)) (PERMUT1 X (CDR W))))))
EXPR)

(DEFPROP PERMUT2
 (LAMBDA(U X V)
  (COND	((NULL V) (LIST (REVERSE (CONS X U))))
	(T (CONS (REV1 (CONS X U) V) (PERMUT2 (CONS (CAR V) U) X (CDR V))))))
EXPR)

(DEFPROP REV1
 (LAMBDA (U V) (COND ((NULL U) V) (T (REV1 (CDR U) (CONS (CAR U) V)))))
EXPR)

(DEFPROP CONN
 (LAMBDA (U) (LESSP (COMP U) 2))
EXPR)

(DEFPROP COMP
 (LAMBDA (U) (LENGTH (MERGCOMPS U)))
EXPR)

(DEFPROP MERGCOMPS
 (LAMBDA (U) (COND ((NULL U) NIL) (T (MERGCOMP (CAAR U) (CAR U) (MERGCOMPS (CDR U))))))
EXPR)

(DEFPROP MERGCOMP
 (LAMBDA(X C L)
  (COND	((NULL L) (LIST C))
	((MEMBER X (CAR L)) (MERGCOMP X (UNION C (CAR L)) (CDR L)))
	(T (CONS (CAR L) (MERGCOMP X C (CDR L))))))
EXPR)

(DEFPROP UNION
 (LAMBDA (U V) (COND ((NULL U) V) ((MEMBER (CAR U) V) (UNION (CDR U) V)) (T (CONS (CAR U) (UNION (CDR U) V)))))
EXPR)